import bisect
from typing import List


class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        ans = [1]
        stack = [obstacles[0]]

        for i in range(1, len(obstacles)):
            j = bisect.bisect_right(stack, obstacles[i])
            if j == len(stack):
                stack.append(obstacles[i])
            else:
                stack[j] = obstacles[i]
            ans.append(j + 1)

        return ans


if __name__ == "__main__":
    print(Solution().longestObstacleCourseAtEachPosition([1, 2, 3, 2]))  # [1,2,3,3]
    print(Solution().longestObstacleCourseAtEachPosition([2, 2, 1]))  # [1,2,1]
    print(Solution().longestObstacleCourseAtEachPosition([3, 1, 5, 6, 4, 2]))  # [1,1,2,3,2,2]
